/**
 * @version Create on 2012-11-13
 * @author Yinzi Chen
 */

public class NQueensII {

	boolean[][] map;
	int[] queen;
	int res, size, top;

	public boolean check(int idx) {
		int p = idx / size, q = idx % size;
		for (int i = 0; i < top; ++i) {
			int x = queen[i] / size, y = queen[i] % size;
			if (map[x][y]
					&& (p == x || q == y || Math.abs(p - x) == Math.abs(q - y)))
				return false;
		}
		return true;
	}

	public boolean prone(int idx) {
		if (idx / size > top)
			return true;
		for (int i = idx / size + 1; i < size; ++i) {
			boolean find = false;
			for (int j = 0; j < size; ++j) {
				if (check(i * size + j)) {
					find = true;
					break;
				}
			}
			if (!find)
				return true;
		}
		return false;
	}

	public void search(int idx) {
		if (idx == size * size) {
			if (top == size)
				res++;
			return;
		}
		if (idx / size > top)
			return;
		// if (prone(idx))
		// return;
		int p = idx / size, q = idx % size;
		if (check(idx)) {
			queen[top++] = idx;
			map[p][q] = true;
			search(idx + 1);
			map[p][q] = false;
			top--;
		}
		search(idx + 1);
	}

	public int totalNQueens(int n) {
		map = new boolean[n][n];
		queen = new int[n];
		top = 0;
		size = n;
		res = 0;
		search(0);
		return res;
	}

	public static void main(String[] args) {
		NQueensII a = new NQueensII();
		System.out.println(a.totalNQueens(12));
	}

}
